package com.duoduo.二分;

/**
 * @author dl.chai
 * @version 1.0
 * @description: 搜索二维矩阵74
 * 编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
 * <p>
 * 每行中的整数从左到右按升序排列。
 * 每行的第一个整数大于前一行的最后一个整数。
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
 * 输出：true
 * 示例 2：
 * <p>
 * <p>
 * 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
 * 输出：false
 * @date 2023/3/24 10:12
 */

public class 搜索二维矩阵74 {
    /**
     * @param matrix
     * @param target
     * @description: 根据题意已知，二维数组从左往右递增，从上往下递增，所以得出以下结论：
     * <p>
     * 某列的某个数字，该数之上的数字，都比其小；
     * 某行的某个数字，该数右侧的数字，都比其大；
     * 所以，解题流程如下所示：
     * <p>
     * 以二维数组左下角为原点，建立直角坐标轴。
     * 若当前数字大于了查找数，查找往上移一位。
     * 若当前数字小于了查找数，查找往右移一位。
     * @return: boolean
     * @date: 2023/3/24 10:57
     */
    public boolean searchMatrix2(int[][] matrix, int target) {
        int x = matrix.length - 1;
        int y = 0;
        //从左下角开始遍历
        while (x >= 0 && y < matrix[0].length) {
            int num = matrix[x][y];
            if (num == target) {
                return true;
            } else if (num > target) {
                x--;
            } else {
                y++;
            }
        }
        return false;
    }

    /**
     * 采用两次二分法，先找出满足条件的行，再找出列就可以了
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;

        // 第一次二分：定位到所在行（从上往下，找到最后一个满足 mat[x]][0] <= t 的行号）
        int l = 0, r = m - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (matrix[mid][0] <= target) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }

        int row = r;
        if (matrix[row][0] == target) return true;
        if (matrix[row][0] > target) return false;

        // 第二次二分：从所在行中定位到列（从左到右，找到最后一个满足 mat[row][x] <= t 的列号）
        l = 0;
        r = n - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (matrix[row][mid] <= target) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        int col = r;

        return matrix[row][col] == target;
    }
}
